/*
 * @lc app=leetcode id=95 lang=cpp
 *
 * [95] Unique Binary Search Trees II
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode *> ret;
        if (n < 1) {
            return ret;
        }

        if (1 == n) {
            ret.push_back(new TreeNode(1));
            return ret;
        }

        return generateTrees(1, n);
    }

    vector<TreeNode *> generateTrees(int m, int n) {

        vector<TreeNode *> ret;
        if (m > n) {
            ret.push_back(NULL);
            return ret;
        }

        if (m == n) {
            ret.push_back(new TreeNode(m));
            return ret;
        }

        for (int i=m; i<=n; i++) {
            vector<TreeNode *> vl = generateTrees(m, i-1);
            vector<TreeNode *> vr = generateTrees(i+1, n);

            for (auto l : vl) {
                for (auto r : vr) {
                    TreeNode *root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    ret.push_back(root);
                }
            }
        }
        return ret;

    }
};

